
"""
912. 排序数组---归并排序
"""
from typing import List


class Solution:

    def __init__(self):
        self.tmp = []

    def sortArray(self, nums: List[int]) -> List[int]:
        self.tmp = [nums[i] for i in range(len(nums))]
        self.gbSort(nums, 0, len(nums) - 1)
        return nums

    """
     * 归并排序
     * 归并排序可以理解为二叉树，先将左子树排序，再将右子树排序，最后再将左右子树合并排序
     * 如何将数组分解为二叉树，以中心点为分割线，将数组分解为二叉树，叶子结点为数组元素
    """
    def gbSort(self, nums: List[int], low, high):
        if low == high:
            return

        # 中心点
        mid = low + int((high - low) / 2)

        # 排序左子树
        self.gbSort(nums, low, mid)
        # 排序右子树
        self.gbSort(nums, mid + 1, high)

        # 合并两个有序数组
        self.mergin_nums(nums, low, mid, high)

    def mergin_nums(self, nums: List[int], low, mid, high):
        i = low
        j = mid + 1
        for k in range(low, high + 1):
           self.tmp[k] = nums[k]

        # 开始合并
        k = low
        while i <= mid or j <= high:
            if i > mid:
                nums[k] = self.tmp[j]
                j += 1
            elif j > high:
                nums[k] = self.tmp[i]
                i += 1
            elif self.tmp[i] < self.tmp[j]:
                nums[k] = self.tmp[i]
                i += 1
            else:
                nums[k] = self.tmp[j]
                j += 1
            k += 1